/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVASE Song Huongkang PROJECT
 * All Rights Reserved.
 */

package Map;

import org.junit.Test;

import java.util.HashMap;

/**
 * @description HashMap
 * 底层实现原理
 *  JDK7：new一个HashMap
 *         HashMap hm1 = new HashMap();
 *          创建了一个长度十六的数组Entry[] table
 *          ...可能执行多次put后...
 *         hm1.put("key1","value1");
 *          首先调用key1的所在类的HashCode()方法计算哈希值，通过算法处理哈希值得到其位置
 *          此位置没有数据 key1,value1 添加成功（实际上是其entry添加成功）
 *          有数据意味着此位置上有一个或多个数据 进行比较这些数据们的哈希值
 *          不同 以链表形式储存
 *          相同 调用key的equals方法 true相同 使用后来的value替换原value
 *                                false不同 添加成功
 *          如达到扩容条件 默认扩容为原来的的2倍
 * JDK8： 除未加入数据时不创建数组(改名为Node[])首次调用时再创建数组 前面过程的一样
 * 只是链表长度超过8且当前的数组长度超过64之后改为由红黑树储存
 * 相应的红黑树的元素少于八个改为链表储存 --->提高了遍历的效率
 *
 *      一些常量
 * DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
 * MAXIMUM_CAPACITY ： HashMap的最大支持容量，2^30
 * DEFAULT_LOAD_FACTOR：HashMap的默认加载因子
 * TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树
 * UNTREEIFY_THRESHOLD：Bucket中红黑树存储的Node小于该默认值，转化为链表
 * MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量。（当桶中Node的
 * 数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY时，此时应执行
 * resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4
 * 倍。）
 * table：存储元素的数组，总是2的n次幂
 * entrySet：存储具体元素的集
 * size：HashMap中存储的键值对的数量
 * modCount：HashMap扩容和结构改变的次数。
 * threshold：扩容的临界值，=容量*填充因子
 * loadFactor：填充因子
 *  HashMap的内部存储结构其实是数组和链表的结合。当实例化一个HashMap时，
 * 系统会创建一个长度为Capacity的Entry数组，这个长度在哈希表中被称为容量
 * (Capacity)，在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个
 * bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。
 *  每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带一个引
 * 用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。
 * 而且新添加的元素作为链表的head。
 *  添加元素的过程：
 * 向HashMap中添加entry1(key，value)，需要首先计算entry1中key的哈希值(根据
 * key所在类的hashCode()计算得到)，此哈希值经过处理以后，得到在底层Entry[]数
 * 组中要存储的位置i。如果位置i上没有元素，则entry1直接添加成功。如果位置i上
 * 已经存在entry2(或还有链表存在的entry3，entry4)，则需要通过循环的方法，依次
 * 比较entry1中key和其他的entry。如果彼此hash值不同，则直接添加成功。如果
 * hash值不同，继续比较二者是否equals。如果返回值为true，则使用entry1的value
 * 去替换equals为true的entry的value。如果遍历一遍以后，发现所有的equals返回都
 * 为false,则entry1仍可添加成功。entry1指向原有的entry元素。
 * HashMap的扩容
 * 当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的
 * 长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在
 * HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算
 * 其在新数组中的位置，并放进去，这就是resize。
 *      那么HashMap什么时候进行扩容呢？
 * 当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数
 * size)*loadFactor 时 ， 就 会 进 行 数 组 扩 容 ， loadFactor 的默认 值
 * (DEFAULT_LOAD_FACTOR)为0.75，这是一个折中的取值。也就是说，默认情况
 * 下，数组大小(DEFAULT_INITIAL_CAPACITY)为16，那么当HashMap中元素个数
 * 超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把
 * 数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，
 * 而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，
 * 那么预设元素的个数能够有效的提高HashMap的性能。
 *      自JDK1.8
 *  HashMap的内部存储结构其实是数组+链表+树的结合。当实例化一个
 * HashMap时，会初始化initialCapacity和loadFactor，在put第一对映射关系
 * 时，系统会创建一个长度为initialCapacity的Node数组，这个长度在哈希表
 * 中被称为容量(Capacity)，在这个数组中可以存放元素的位置我们称之为
 * “桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查
 * 找bucket中的元素。
 *  每个bucket中存储一个元素，即一个Node对象，但每一个Node对象可以带
 * 一个引用变量next，用于指向下一个元素，因此，在一个桶中，就有可能
 * 生成一个Node链。也可能是一个一个TreeNode对象，每一个TreeNode对象
 * 可以有两个叶子结点left和right，因此，在一个桶中，就有可能生成一个
 * TreeNode树。而新添加的元素作为链表的last，或树的叶子结点。
 *
 *  那么HashMap什么时候进行扩容和树形化呢？
 * 当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数
 * size)*loadFactor 时 ， 就会进行数组扩容 ， loadFactor 的默认 值
 * (DEFAULT_LOAD_FACTOR)为0.75，这是一个折中的取值。也就是说，默认
 * 情况下，数组大小(DEFAULT_INITIAL_CAPACITY)为16，那么当HashMap中
 * 元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）
 * 的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元
 * 素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知
 * HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
 * 当HashMap中的其中一个链的对象个数如果达到了8个，此时如果capacity没有
 * 达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成
 * 树，结点类型由Node变成TreeNode类型。当然，如果当映射关系被移除后，
 * 下次resize方法时判断树的结点个数低于6个，也会把树再转为链表。
 *
 *  关于映射关系的key是否可以修改？answer：不要修改
 *      映射关系存储到HashMap中会存储key的hash值，这样就不用在每次查找时重新计算
 *      每一个Entry或Node（TreeNode）的hash值了，因此如果已经put到Map中的映射关
 *      系，再修改key的属性，而这个属性又参与hashcode值的计算，那么会导致匹配不上。
 *
 *  总结：JDK1.8相较于之前的变化：
 * 1.HashMap map = new HashMap();//默认情况下，先不创建长度为16的数组
 * 2.当首次调用map.put()时，再创建长度为16的数组
 * 3.数组为Node类型，在jdk7中称为Entry类型
 * 4.形成链表结构时，新添加的key-value对在链表的尾部（七上八下）
 * 5.当数组指定索引位置的链表长度>8时，且map中的数组的长度> 64时，此索引位置
 * 上的所有key-value对使用红黑树进行存储。
 *
 * @author 俊昭
 * @date 2022/4/20
*/
public class HashMapTest {
    @Test
    public void test01(){
//         new一个HashMap
        HashMap hm1 = new HashMap();
//         创建了一个长度十六的数组Entry[] table
//         ...可能执行多次put后...
        hm1.put("key1","value1");
//         首先调用key1的所在类的HashCode()方法计算哈希值，通过算法处理哈希值得到其位置
//         此位置没有数据 key1,value1 添加成功（实际上是其entry添加成功）
//         有数据意味着此位置上有一个或多个数据 进行比较这些数据们的哈希值
//         不同 以链表形式储存
//         相同 调用key的equals方法 true相同 使用后来的value替换原value
//                               false不同 添加成功



    }
}
